package bubblesort

//BubbleSort 冒泡算法 稳定的排序算法
//平均：O(n^2) 最差：O(n^2) 最好：O(n)
func BubbleSort(list []int) []int  {
	ln := len(list)
	for i := 1; i < ln; i++ {
		isSorted := true
		for j := 1; j <= ln-i; j++ {
			if list[j-1] > list[j] {
				list[j-1],list[j] = list[j],list[j-1]
				isSorted = false
			}
		}
		if isSorted { //如果后面都是排好序的，就不用再排了，这时候就是最好情况O(n)
			break
		}
	}
	return list
}